package com.husd.leetcode.dynamic;

/**
 * 跳台阶问题
 * <p>
 * 一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个n级台阶总共有多少种跳法。
 * <p>
 * 1、判题题意是否为找出一个问题的最优解
 * 这个我还真的看不出，直觉判断这题可以通过动态规划迭代出来….有经验的网友可以分享下看法，指导一下本小白白。
 * <p>
 * 2、从上往下分析问题，大问题可以分解为子问题，子问题中还有更小的子问题
 * 题目中没有给粟子，我们可以自己举点粟子。例如，跳上一个6级台阶台阶，有多少种跳法；由于青蛙一次可以跳两阶，也可以跳一阶，所以我们可以分成两个情况
 * 1、青蛙最后一次跳了两阶，问题变成了“跳上一个4级台阶台阶，有多少种跳法”
 * 2、青蛙最后一次跳了一阶，问题变成了“跳上一个5级台阶台阶，有多少种跳法”
 * 由上可得f(6) = f(5) + f(4);
 * 由此类推，f(4)=f(3) +f(2)
 * <p>
 * 3.、从下往上分析问题 ，找出这些问题之间的关联（状态转移方程）
 * 跟上面的例题一相同，可以由f(1)逐渐迭代上去
 * 由2可得，状态转移方程为：f(n)=f(n-1)+f(n-2)
 * <p>
 * 4、边界情况分析
 * 跳一阶时，只有一种跳法，所以f(1)=1
 * 跳两阶时，有两种跳法，直接跳2阶，两次每次跳1阶，所以f(2)=2
 * 跳两阶以上可以分解成上面的情况
 * ————————————————
 * 版权声明：本文为CSDN博主「食鱼酱」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
 * 原文链接：https://blog.csdn.net/weixin_38278878/java/article/details/80037455
 *
 * @author hushengdong
 * @date 2020/3/31
 */
public class Jump {

    public int maxJump(int n) {

        if (n <= 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        int[] step = new int[n + 1];
        step[0] = 0;
        step[1] = 1;
        step[2] = 2;
        for (int i = 3; i <= n; i++) {
            //N个台阶，可以从N-1或者N-2处跳上来
            step[i] = step[i - 1] + step[i - 2];
        }
        return step[n];
    }
}
